package com.chenchao.javaarray;

/**
 * @encoding : UTF-8
 * @Time : 2020/11/9 16:39
 * @Author : Chen Chao
 * @File : javaSE.com.chenchao.javaarray.Test3.java
 * @Software : IntelliJ IDEA
 * @since : 1.8
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(upper_bound_(7, 3, new int[]{0, 0, 1, 2, 3, 4, 5}));
    }

    /**
     * upper_bound_  输出在数组中第一个大于等于查找值的位置，如果数组中不存在这样的数，则输出数组长度加一。
     *
     * @param n
     * @param v
     * @param a
     * @return
     */
    public static int upper_bound_(int n, int v, int[] a) {
        // write code here
        int startIndex = 0;
        int endIndex = n - 1;
        int midIndex = (startIndex + endIndex) / 2;
        if (v > a[n - 1]) {
            return n + 1;
        }
        while (startIndex < endIndex) {
            if (a[midIndex] >= v) {
                endIndex = midIndex;
            } else if (a[midIndex] < v) {
                startIndex = midIndex + 1;
            }
            midIndex = startIndex + (endIndex - startIndex) / 2;
        }
        return midIndex + 1;
    }
}
